LiDAR (Light Detection And Ranging, also referred to as “LADAR”) is an optical remote sensing technology used to measure the distance to, or other properties of, a target by illuminating the target with light, often using pulses from a laser. LiDAR technology has application in geomatics, archaeology, geography, geology, geomorphology, seismology, forestry, remote sensing and atmospheric physics, as well as in airborne laser swath mapping (ALSM), laser altimetry and LiDAR contour mapping.
LiDAR may use ultraviolet, visible, or near infrared light to image objects and may be used with a wide range of targets, including non-metallic objects, rocks, rain, chemical compounds, aerosols, clouds and even single molecules. A narrow laser beam may be used to map physical features with very high resolution. LiDAR has been used extensively for atmospheric research and meteorology. Downward-looking LiDAR instruments fitted to aircraft and satellites may be used for surveying and mapping, a recent example being the NASA Experimental Advanced Research LiDAR.
Wavelengths in the range of about 10 micrometers to the UV (ca. 250 nm) may be used to suit the target. Typically light is reflected via backscattering. Different types of scattering are used for different LiDAR applications; common types include Rayleigh scattering, Mie scattering and Raman scattering, as well as fluorescence. Based on the type of backscattering used, the LiDAR may be accordingly referred to as Rayleigh LiDAR, Mie LiDAR, Raman LiDAR and Na/Fe/K Fluorescence LiDAR and so on.
In some LiDAR systems, the distance to a remote object may be determined based on the time delay between transmission of the laser pulse and detection of the reflection of the pulse as described, for example, in U.S. Pat. Nos. 7,746,449 and 7,701,558, which are hereby incorporated herein for all purposes. Additional information about detected remote objects may be obtained by analysis of the reflected signal as described in U.S. Pat. No. 7,187,452, which is also hereby incorporated herein for all purposes.
By utilizing a relatively short wavelength signal, LiDAR is able to be used to achieve a high level of accuracy in detecting remote objects and may be used to make over 200,000 measurements per second using currently available commercial LiDAR systems. As such, LiDAR is capable of capturing relatively large amounts of highly accurate and dense data in a very short period of time. Another example of a similar LiDAR system is described in U.S. Pat. No. 5,988,862 which is hereby incorporated herein for all purposes.
Among various LiDAR systems, Airborne LiDAR is especially important for gathering information about the Earth's surface. In such systems, a LiDAR data scanner may be mounted on an airborne platform. The current position of the LiDAR scanner may be determined using a global positioning system (GPS), while an inertial measurement unit (IMU) may be used to measure the roll, pitch and heading of the aircraft to establish an angular orientation of the LiDAR sensor. Using the angular orientation of the LiDAR sensor and by measuring the scan angle, the angular orientation of emitted laser pulses are established and the precise positions of surveyed points can be accurately defined. Recorded points may then be projected onto one of the local geographic coordinate systems (e.g., the Gauss-Kruger coordinate system) or a global geographic coordinate system (e.g., the Universal Transverse Mercator coordinate system). Furthermore, because the LiDAR systems are capable of distinguishing between different reflections of the emitted laser pulse points, the Earth's surface, even below vegetation, can be mapped. A more detailed explanation of how LiDAR operates may be found, for example, in Maune, D. F. “Aerial mapping and surveying” found in “Land Development Handbook: Planning, Engineering, and Surveying, Third Edition”, Sidney O. Dewberry and L. N. Rauenzahn (Eds), pp. 877-910, New York, McGraw-Hill Professional, 2008 which is hereby incorporated herein for all purposes.
The leading open (i.e., non-proprietary) industrial standard for storing and exchanging data collected by LiDAR systems is defined in the “LAS Specification” published by The American Society for Photogrammetry & Remote Sensing (ASPRS), based in Bethesda, Md. This specification is an open binary file format that details LASer (LAS) file format data exchange information. Although there are slight differences between different revisions of the LAS file format specifications, these specifications all prescribe points to be represented by xyz-coordinates and associated scalar values (e.g., intensity of reflected signal, a color of a point, or user specific data). Because of the capabilities of the LiDAR systems, LAS files often contain several tens of millions of points and the file size can easily exceed a few gigabytes per square kilometer mapped. Storage of LAS files may therefore be expensive and file exchange over local networks and the Internet may become impractical. Because of these factors, an efficient compression method for LiDAR data is needed.
Entropy encoding algorithms may be used for this purpose. For example, U.S. Pat. Nos. 5,418,532, 5,546,080, and 7,737,870 (all of which are hereby incorporated herein by reference for all purposes) describe some of the many general purpose compression methods. Other publications may also be consulted, for example Huffman, “A Method for the Construction of Minimum-Redundancy Codes”, Proc. of the I.R.E., pp. 1098-1102, 1952, and Rissanen & Langdon “Arithmetic coding”, IBM Journal of Research and Development, 23(2), pp. 149-162, 1979, both of which are hereby incorporated herein by reference for all purposes. Still, the entropy encoding algorithms are not efficient when compressing geometrical data. For this purpose, domain specific algorithms have been introduced.
However, geometrical data compression is still a relatively new area. One of the earliest methods has been presented in Taubin & Rossignac “Geometric compression through topological surgery”, ACM Transactions on Graphics, 17, pp. 84-115, 1998, which is hereby incorporated herein by reference for all purposes. The method compresses the geometry of the triangle mesh as well as the topology. For this purpose, the triangle mesh is divided into triangular strips. The vertices are arranged according to their appearances in the triangular strips and coded with a linear prediction schema. Instead of storing the absolute coordinates, only differences between the predicted and the actual positions of vertices are stored. Similar methods that achieve geometrical data compression by forming triangle meshes are also described in U.S. Pat. Nos. 5,793,371; 5,867,167; 5,870,094; 6,239,805; 6,314,205; and Publication Nos. WO/2000/077740 and US 2002050992; and in other publications, for example Deering, “Geometry compression”, Proc. of the 22nd annual conference on Computer graphics and interactive techniques, pp. 13-20, 1995, all of which are hereby incorporated herein by reference for all purposes. Still, due to a need for the topology, these methods cannot be directly applied to LiDAR datasets.
Thus, what is needed are methods and apparatus for compressing three dimensional (3D) datasets (e.g., LAS data files) using domain-specific information about the 3D data scanning.